package interview.huawei.tjt.training.huisu;

/**
 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 *
 * 返回 s 所有可能的分割方案。
 *
 * 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
 *
 *Deque:
 *   deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。
 *   但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。
 */
import java.util.*;

public class FenGeHuiWenChuan {

    private static List<Deque<String>> result = new ArrayList<>();
    private static Deque<String> deque = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            helper(s,0);
            System.out.println(result);
            result.clear();
        }
    }

    private static void helper (String s,int startIndex) {
        // 终止条件
        if (startIndex >= s.length() ) {
            result.add(new ArrayDeque<>(deque));
            return;
        }

        for (int i = startIndex; i < s.length(); i ++ ) {
            if (isPalindrome(s,startIndex,i)) {
                String str = s.substring(startIndex,i + 1);
                deque.addLast(str);
            } else {
                continue;
            }

            helper(s, i + 1);
            deque.removeLast();
        }
    }

    // 判断是否为回文串
    private static boolean isPalindrome (String s,int start,int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            } else {
                return true;
            }
        }
        return true;
    }

}
